<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>

    </style>
</head>

<body>


    <script>
        // function hashCode(str, max) {
        //     let hashCode = 0;
        //     for (let i = 0; i < str.length; i++) {
        //         hashCode = 31 * hashCode + str[i].charCodeAt();
        //     }
        //     hashCode = hashCode % max;
        //     return hashCode
        // }
        // console.log(hashCode("aa", 10));
        // console.log(hashCode("bb", 10));
        // console.log(hashCode("cc", 10));
        // console.log(hashCode("dd", 10));
        // var str = ["a","b","c"]
        // for(let i = 0; i < str.length; i++) {
        //     console.log(str[i].charCodeAt());
        // }

        //判断是否是质数
        function isPrime(num) {
            //获取num的平方根
            let temp = Math.ceil(Math.sqrt(num));
            //遍历循环
            for (let i = 2; i < temp; i++) {
                if (num % i === 0) {
                    return false;
                }
            }
            return true;
        }


        const MAX_LOAD_FACTOR = 0.75;
        const MIN_LOAD_FACTOR = 0.25;
        class HashTable {
            constructor() {
                this.storage = [];//数组存储元素
                this.count = 0; //当前存放了多少个元素
                this.limit = 7; //总个数
            }

            //哈希函数
            hashFunc(str, max) {
                let hashCode = 0;
                for (let i = 0; i < str.length; i++) {
                    hashCode = 31 * hashCode + str[i].charCodeAt();
                }
                hashCode = hashCode % max;
                return hashCode;
            }

            //放入元素：HashMap -> {key: value}
            put(key, value) {
                //1.根据key获取到下标，函数
                const index = this.hashFunc(key, this.limit);
                //2.取出数组
                let bucket = this.storage[index];
                // console.log(this.storage[index]);
                if (bucket === undefined) {
                    bucket = [];
                    this.storage[index] = bucket;
                }
                //3.判断是插入还是修改操
                let overide = false;
                for (let i = 0; i < bucket.length; i++) {
                    let tuple = bucket[i];
                    if (tuple[0] === key) {
                        tuple[1] = value;
                        overide = true;
                    }
                }
                //4.如果没有覆盖，那么就是新增
                if (!overide) {
                    bucket.push([key, value])
                    this.count++;

                    if (this.count > this.limit * MAX_LOAD_FACTOR) {
                        let newLimit = this.limit * 2;
                        // newLimit = this.getPrime(newLimit);
                        // this.resize(newLimit);
                        this.resize(this.getPrime(newLimit));
                    }
                }
            }

            //根据key获取value
            get(key) {
                // 1.根据key获取index
                const index = this.hashFunc(key, this.limit);   //秦九韶算法hashFunc获取到下标
                let bucket = this.storage[index];//创建一个桶用于存放
                if (bucket !== undefined) {  //有可能获取到undefined因为可能会超出原来数组大小
                    for (let i = 0; i < bucket.length; i++) {
                        let tuple = bucket[i];
                        if (tuple[0] === key) {
                            return tuple[1];
                        }
                    }
                } else return null;
            }

            //remove 删除元素
            remove(key) {
                const index = this.hashFunc(key, this.limit);
                let bucket = this.storage[index];
                if (bucket !== undefined) {
                    for (let i = 0; i < bucket.length; i++) {
                        let tuple = bucket[i];
                        if (tuple[0] === key) {
                            bucket.splice(i, 1);
                            this.count--;

                            if (this.limit > 8 && this.count < this.limit * MIN_LOAD_FACTOR) {
                                let newLimit = Math.floor(this.limit / 2)
                                newLimit = this.getPrime(newLimit)
                                this.resize(newLimit);
                            }
                        }
                    }
                } else return null;
            }

            //isEmpty() 判断表是否为空 为空就返回true
            isEmpty() {
                return this.count === 0;
            }

            //size() 判断hash长度
            size() {
                return this.count;
            }

            //resize()扩容 有可能要缩小容量
            resize(newLimit) {
                //1.保留旧的数组的内容
                let oldStorage = this.storage;
                //2.重置属性
                this.limit = newLimit;
                this.storage = [];
                this.count = 0;
                //3.取出oldStorage里面的所有元素，重新放入到storage里面
                oldStorage.forEach((bucket) => {
                    if (bucket === undefined) {
                        return
                    }
                    for (let i = 0; i < bucket.length; i++) {
                        let tuple = bucket[i];
                        this.put(tuple[0], tuple[1])
                    }
                })
            }

            //判断是否是质数
            isPrime(num) {
                //1.向上去整取平方根
                let temp = Math.ceil(Math.sqrt(num));
                //2.进行判断书否为质数
                for (let i = 2; i <= temp; i++) {
                    if (num % i === 0) {
                        return false;
                    }
                }
                return true;
            }

            //getPrime(num)获得一个质数
            getPrime(num) {
                while (!this.isPrime(num)) {
                    num++;
                }
                return num;
            }

        }

        const hashTable = new HashTable();
        hashTable.put("name", "leilei")
        hashTable.put("name1", "leilei")
        hashTable.put("name2", "leilei")
        hashTable.put("name3", "leilei")
        // hashTable.put("age", 18);
        // hashTable.put("hight", 1.88);
        // hashTable.put("hight1", 1.88);
        // hashTable.put("hight9", 1.88);
        // hashTable.put("hight2", 1.88);   
        // hashTable.put("hight4", 1.88);
        // hashTable.put("hight5", 1.88);
        // hashTable.put("hight6", 1.88);
        // hashTable.put("hight8", 1.88);
        // hashTable.put("hight10", 1.88);
        // hashTable.put("hight11", 1.88);
        // hashTable.put("hight12", 1.88);
        // hashTable.put("hight13", 1.88);
        // hashTable.put("hight14", 1.88);
        // hashTable.put("hight15", 1.88);
        // hashTable.remove("name")
        // hashTable.remove("name1")
        // hashTable.remove("hight1");
        // hashTable.remove("name2");
        // hashTable.remove("name3")
        console.log(hashTable);
        console.log(hashTable.count);

        // hashTable.remove("hight")
        // hashTable.remove("hight1")
        // hashTable.remove("hight9")
        // hashTable.remove("hight2")
        // hashTable.remove("hight4")
        // hashTable.remove("name")
        // console.log(hashTable.storage);
        // console.log(hashTable.count);

        // hashTable.resize(9)
        // console.log(hashTable.get("name"));
        // console.log(hashTable.isEmpty());
        // console.log(hashTable.size());
        // const nums = [];
        // console.log(nums === undefined);

        // let sum = [0,1,2,3,4]
        // // console.log(sum);
        // sum.forEach((i) => {
        //     console.log(i);
        // })

        console.log(Math.sqrt(4));
        console.log(hashTable.isPrime(4));
        let tmp = Math.ceil(Math.sqrt("9"));
        console.log(tmp);


        console.log(hashTable.getPrime(2));
    </script>
</body>

</html>